Characterisation of Non-Unique Base \(b\)-expansions

There are many proofs in which working with the expansions of real numbers in a given base feels like it would give the nicest argument, however the non-uniqueness of such expansions often leads to problems.

It seems though that this non-uniqueness is localised to a particular type of problem. In base \(10\), considering non-unique expansions seem to all be (loosely speaking) of the same form:

\[\begin{align*} 0.99900\dots &= 1.00000\dots \\ 0.05999\dots &= 0.06000\dots \\ 0.00199\dots &= 0.00200\dots \\ \end{align*}\]

Indeed this is the case, and the following theorem describes this rigorously to classify non-unique expansions completely.

We isolate the problem here such that proofs like the uncountability of the real numbers can handle these issues.

Theorem

Let \(x, y \in [0, 1)\), and let \(x_n\) and \(y_n\) be the corresponding digits of each number in their base \(b\) expansion (after the decimal point, starting index at \(1\)). That is, \(x_n, y_n \in \{0, \dots, b - 1\}\) for all \(n \geq 1\).

If the base \(b\) expansions of \(x\) and \(y\) given above are distinct, then we have that \(x = y\) if and only if (up to reordering) there exists an \(N\) such that

  1. \(n < N \implies x_n = y_n\)
  2. \(n = N \implies x_n = y_n - 1\)
  3. \(n > N \implies x_n = b - 1 \land y_n = 0\)
Proof

Assume that \(x = y \in [0, 1)\), and write \(x = \sum_{k = 1}^\infty x_k b^{-k}\) and \(y = \sum_{k = 1}^\infty x_k b^{-k}\), the base \(b\) expansions of each \(x\) and \(y\), which are distinct.

Let \(N\) be the least positive integer such that \(x_N \neq y_N\). Now consider that

\[\begin{align*} 0 = y - x &= \sum_{k = 1}^\infty y_k b^{-k} - \sum_{k = 1}^\infty x_k b^{-k} \\ &= \sum_{k = 1}^\infty (y_k - x_k) b^{-k} \\ &= \sum_{k = N}^\infty (y_k - x_k) b^{-k} \\ &= (y_N - x_N)b^{-N} + \sum_{k = N + 1}^\infty (y_k - x_k) b^{-k} \\ &\leq (y_N - x_N)b^{-N} + (b - 1)\sum_{k = N + 1}^\infty b^{-k} \\ &= (y_N - x_N)b^{-N} + (b - 1)\frac{\frac{1}{b^{-(N + 1)}}}{1 - \frac{1}{b}} \\ &= (y_N - x_N)b^{-N} + \frac{1}{b^N} \\ \end{align*}\]

hence

\[ 0 \leq (y_N - x_N)b^{-N} + \frac{1}{b^N} = (y_N - x_N + 1)b^{-1}\]

and therefore

\[ y_N - x_N + 1 \geq 0 \implies y_N - x_N \geq -1 \implies x_N - y_N \leq 1.\]

The symmetrical argument above similarly shows that \(x_N - y_N \leq 1\) and hence we have that \(|x_N - y_N| \leq 1\). Since we assumed that \(x_N \neq y_N \implies x_N - y_N \neq 0\), we have that \(|x_N - y_N| = 1\). As such, we assume without loss of generality that \(x_N = y_N - 1\) (the other argument follows identically).

Returning to our calculation of the difference, we now have that

\[\begin{align*} 0 = x - y &= (x_N - y_N)b^{-N} + \sum_{k = N + 1}^\infty (x_k - y_k) b^{-k} \\ &= -b^{-N} + \sum_{k = N + 1}^\infty (x_k - y_k) b^{-k} \\ b^{-N} &= \sum_{k = N + 1}^\infty (x_k - y_k) b^{-k}. \\ \end{align*}\]

We know that the right hand side is upper bounded by \(b^{-N}\) and since this is the left hand side, equality happens when the right hand side achieves this upper bound. If any \(x_k - y_k\) is not \(b - 1\) then the sum can be at most \(b^{-N} - ((b - 1) - (x_k - y_k))b^{-k}\). For example in base \(10\), if one digit is \(8\), in the \(k^{\text{th}}\) place, then the sum is bounded by \(10^{-N} - 8\cdot 10^{-k}\). As such we have that \(x_k - y_k = b - 1\) for all \(k > N\). Since \(x_k\) and \(y_k\) are in \(\{0, \dots, b - 1\}\), the only way this is possible is by maximising \(x_k\) and minimising \(y_k\), that is \(x_k = b - 1\) and \(y_k = 0\) for all \(k > N\).

This proves the forward implication.

Reverse implication is relatively straightforward. That is, if we assume that

  1. \(n < N \implies x_n = y_n\)
  2. \(n = N \implies x_n = y_n - 1\)
  3. \(n > N \implies x_n = b - 1 \land y_n = 0\)

as above, then we have that

\[\begin{align*} x - y &= \sum_{k = 1}^\infty x_k b^{-k} - \sum_{k = 1}^\infty y_k b^{-k} \\ &= \sum_{k = 1}^\infty (x_k - y_k) b^{-k} \\ &= \sum_{k = N}^\infty (x_k - y_k) b^{-k} \\ &= -b^{-N} + \sum_{k = N + 1}^\infty (b - 1) b^{-k} \\ &= -b^{-N} + b^{N} \\ &= 0. \\ \end{align*}\]